11504 - Dominos/11504.cpp

   1 /*
   2   Problem: 11504 - Dominos
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6  */
   7
   8 using namespace std;
   9 #include <iostream>
  10 #include <vector>
  11 #include <cassert>
  12
  13 const int N = 100005;
  14
  15 vector<int> g[N];
  16 int color[N];
  17
  18 enum { standing, tiled, handed };
  19
  20 void dfs(int u, int root){
  21   if (color[u] != standing) return;
  22
  23   if (u == root) color[u] = handed;
  24   else color[u] = tiled;
  25
  26   vector<int> &out = g[u];
  27   for (int k=0, m=out.size(); k<m; ++k){
  28     int v = out[k];
  29     if (color[v] == handed && v != root) color[v] = tiled;
  30     else if (color[v] == standing) dfs(v, root);
  31   }
  32 }
  33
  34 int main(){
  35   int t;
  36   for(cin >> t; t--;){
  37     int n, m; cin >> n >> m;
  38
  39     assert(n < N && m < N);
  40
  41     for (int i=0; i<=n; ++i) g[i].clear(), color[i] = standing;
  42     for (int u, v, i=0; i<m && cin >> u >> v; ++i) g[u].push_back(v);
  43     for (int i=1; i<=n; ++i) if (color[i] == standing) /*printf("Calling dfs(%d)...\n", i),*/ dfs(i, i);
  44
  45     int ans = 0;
  46     for (int i=1; i<=n; ++i){
  47       //if (color[i] == handed) printf("Knock down tile %d\n", i);
  48       ans += (color[i] == handed);
  49     }
  50
  51     cout << ans << endl;
  52   }
  53   return 0;
  54 }